/**
 * There is an integer array nums sorted in non-decreasing order (not necessarily
 * with distinct values).
 * <p>
 * Before being passed to your function, nums is rotated at an unknown pivot
 * index k (0 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1],
 * ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1
 * ,2,4,4,4,5,6,6,7] might be rotated at pivot index 5 and become [4,5,6,6,7,0,1,2,
 * 4,4].
 * <p>
 * Given the array nums after the rotation and an integer target, return true if
 * target is in nums, or false if it is not in nums.
 * <p>
 * You must decrease the overall operation steps as much as possible.
 * <p>
 * <p>
 * Example 1:
 * Input: nums = [2,5,6,0,0,1,2], target = 0
 * Output: true
 * <p>
 * Example 2:
 * Input: nums = [2,5,6,0,0,1,2], target = 3
 * Output: false
 * <p>
 * <p>
 * Constraints:
 * <p>
 * <p>
 * 1 <= nums.length <= 5000
 * -10⁴ <= nums[i] <= 10⁴
 * nums is guaranteed to be rotated at some pivot.
 * -10⁴ <= target <= 10⁴
 * <p>
 * <p>
 * <p>
 * Follow up: This problem is similar to Search in Rotated Sorted Array, but nums
 * may contain duplicates. Would this affect the runtime complexity? How and why?
 * <p>
 * Related Topics 数组 二分查找 👍 667 👎 0
 */


package com.xixi.basicAlgroithms.binarySearch;

public class ID00081SearchInRotatedSortedArrayIi {
    public static void main(String[] args) {


        Solution solution = new ID00081SearchInRotatedSortedArrayIi().new Solution();
        solution.search(new int[]{1, 0, 1, 1, 1}, 0);
    }


    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public boolean search(int[] nums, int target) {
            int len = nums.length;

            int left = 0;
            int right = len - 1;

            while (left <= right) {
                int mid = left + (right - left) / 2;

                if (nums[mid] == target) return true;


                //需要确定数据在左半段还是右半段，左半段mid >= left, 右半段mid <=right
                //如果碰到mid == left && mid == right， 得排除干扰项。缩小范围
                if (nums[mid] == nums[left] && nums[mid] == nums[right]) {
                    left++;
                    right--;
                } else if (nums[left] <= nums[mid]) { //左区间有序
                    if (nums[left] <= target && nums[mid] > target) { //target 在mid 左边的唯一情况
                        right = mid - 1;
                    } else if (nums[left] > target || nums[mid] < target) {// target 在 mid 左边
                        left = mid + 1;
                    }
                } else if (nums[left] > nums[mid]) { // 右区间有序
                    if (nums[mid] < target && nums[right] >= target) {
                        left = mid + 1;
                    } else {
                        right = mid - 1;
                    }
                }

            }

            return false;

        }
    }
//leetcode submit region end(Prohibit modification and deletion)


}